<?php

class Point
{
	public function __construct($x, $y)
	{
		$this->x = $x;
		$this->y = $y;
	}

	public $x;
	public $y;
}

class Size
{
	public function __construct($width, $height)
	{
		$this->width = $width;
		$this->height = $height;
	}

	public $width;
	public $height;
}

class Bounds
{
	public function __construct($location, $size)
	{
		$this->location = $location;
		$this->size = $size;
	}

	public $location;
	public $size;
}

// Input entry to place in the grid.
class GridEntry
{
	public function __construct($weight)
	{
		$this->weight = $weight;
	}

	// The weight is a number between 0 and 1.
	public $weight;
	// Title of the article, if any.
	public $title;
}

// Output item of the grid.
class GridNewnit
{
	// Location of the newnit.
	public $bounds;
	// Source grid entry.
	public $gridEntry;
}

// Used to layout grid entries into the grid.
class GridLayouter
{
	private $newnits;
	private $grid;
	private $entries;
	private $wildZones;

	private static function entryCompare($e1, $e2)
	{
		return $e1->weight > $e2->weight;
	}
	
	/// Try to place the remaining entries in the grid.
	public function tryPlace()
	{
		// Stopping condition: all entries has been placed successfully.
		if (count($this->entries) == 0)
			return true;
			
		// Stopping condition: there is no wild zone to place the entry.
		if (count($this->wildZones) == 0)
			return false;
		
		// We grab the largest entry.
		$localEntry = array_pop($this->entries);
		$wildZone = array_pop($this->wildZones);
		$bounds = clone $wildZone;
	
		// First try: in the whole bounds
		// We take the first wildzone to fit the remaining
		if ($this->tryPlace())
		{
			$localNewnit = new GridNewnit();
			$localNewnit->bounds = $bounds;
			$localNewnit->entry = $localEntry;
		
			array_push($this->newnits, $localNewnit);
			return true;
		}
				
		// Main loop: we try to place the entry and the subentries
		// until it all fits nicely
		do
		{	    
			// Slice the local bounds in two parts:
			//		- one became the new local bounds
			//		- the other become a new wild zone
			if ($bounds->size->width > $bounds->size->height)
			{
				$sourceWidth = $bounds->size->width;
				$bounds->size->width = ceil($bounds->size->width / 2);
				$newWildZone = new Bounds(new Point($bounds->location->x + $bounds->size->width,
					$bounds->location->y), new Size($sourceWidth - $bounds->size->width, $bounds->size->height));
			}
			else
			{
				$sourceHeight = $bounds->size->height;
				$bounds->size->height = ceil($bounds->size->height / 2);
				$newWildZone = new Bounds(new Point($bounds->location->x,
					$bounds->location->y + $bounds->size->height),
					new Size($bounds->size->width, $sourceHeight - $bounds->size->height));
			}
			
			// Stopping condition: there no way to place all entries...
			if ($newWildZone->size->width == 0 || $newWildZone->size->height == 0)
			{
			    // Just restore the entry and wild zones
			    array_push($this->entries, $localEntry);
			    array_push($this->wildZones, $wildZone);
				return false;
			}
			
			// Add the new wildzone
			array_push($this->wildZones, $newWildZone);
			
			// Try to place the remaining entries, taking in account the new wild zone
		} while (!$this->tryPlace());
		
		$localNewnit = new GridNewnit();
		$localNewnit->bounds = $bounds;
		$localNewnit->entry = $localEntry;
	
		array_push($this->newnits, $localNewnit);
		
		return true;
	}
	
	
	public function layout($entries, $gridSize)
	{
		$this->newnits = array ();
		$this->grid = array ();
		
		$this->entries = $entries;
		usort($this->entries, 'GridLayouter::entryCompare');
		
		// We start with the first entry and we want to fill the whole grid
		$this->wildZones = array(new Bounds(new Point(0, 0), clone $gridSize));
		$this->tryPlace();
		
		return $this->newnits;
	}

}
